package learn.juc.custom;

import java.util.Random;

/**
 * 跳跃表实现
 */
public class SkipList {
    class SkipNode<T> {
        // 数据区
        public Integer score;
        public T value;

        // 当前节点的 上下左右层级节点
        public SkipNode up;
        public SkipNode down;
        public SkipNode left;
        public SkipNode right;

        public SkipNode(Integer score, T value) {
            this.score = score;
            this.value = value;
        }
    }

    // 节点数量
    public int num;

    // 最高层数
    public int max_hight;

    public SkipNode head;
    public SkipNode tail;

    // 概率随机
    private Random random;

    public SkipList() {
        this.max_hight = 6; // 设置最高层数为6层
        this.num = 0; // 初始化时没有节点 这里设置 0
        this.head = new SkipNode(Integer.MIN_VALUE, null);
        this.tail = new SkipNode(Integer.MAX_VALUE, null);
        this.random = new Random();
        this.head.right = tail; // 将链表 头节点与尾节点关联
        this.tail.left = head;
    }

    /**
     * 基本操作   增加， 删除， 查找
     * 但是 这些操作都离不开 查询， 首先要定位到数据 然后再进行 其他操作
     */

    // 查找 , 根据指定的分数值查找数据
    private SkipNode find(Integer score) {
        SkipNode start = this.head;
        while (true) {
            // 如果当前 节点的右节点 score 比要查询的小则 往右移动， 直到遇见比它大的
            // 这里进来会一直往右去找
            while (start.right.score <= score) {
                start = start.right;
            }

            // 如果已经定位到 当前这一层 右节点比要查询的大了 ， 那么将向下定位 ，这里判断下一层是否为null 不为null 则继续定位
            if (start.down != null) {
                start = start.down;
            } else {
                break;
            }
        }
        return start;  // 注意 这里 start.score 分值是小雨等于 传入的 score 值
        // 注意 这里 是小于等于 score值 ，右2种情况
        // 1 如果查找的分值 存在，则返回该对象的底层节点；
        // 2 如果查找的分值 不存在 ，则返回 最接近该对象的底层节点
    }

    // get操作 这里就可以获取 传入分数对应的节点， 如果完全匹配 那么返回该节点对应的value ， 不匹配 则 return null;
    public Object get(Integer score) {
        if (num < 1) {
            return null;
        }
        SkipNode mark = find(score);
        if (mark.score.equals(score)) {
            return mark.value;
        } else {
            return null;
        }
    }

    public void put(Integer score, Object value) {
        // 寻找对应的 分值，如果不存在 则返回最近位置的分值 ，等于已经找到合适的插入位置
        SkipNode mark = find(score);
        // 如果找的节点分值 与要穿入的 相等 那么表示已存在，则进行更新
        if (mark.score.equals(score)) {
            mark.value = value;
            return;
        }
        // 否则 进行插入
        SkipNode brand_new = new SkipNode<>(score, value);
        // 要在 查询到的 mark 右边进行插入，
        // 即 新增的 节点 左边为 查询到的mark。  右边为 原来mark 的右边节点
        brand_new.left = mark;
        brand_new.right = mark.right;
        // 原来 mark 右边节点的左节点更新为 新创建的节点。  将mark 的右节点 更新为 新创建的节点
        mark.right.left = brand_new;
        mark.right = brand_new;

        // 使用变量标识 层级
        int i = 0;
        while (random.nextDouble() < 0.5) {
            if (i > max_hight) {
                break;
            }
            // 这里 mark 在查询到的时候 已经是最下层 包含所有节点的 那一层的数据了， 然后这里 获取它的上层，看是否存在更高层
            // 如果不存在，那么就切换到左边一个节点继续便利， 一直到获取到存在最高层的 节点
            while (mark.up == null) {
                mark = mark.left;
            }
            // 找到左侧存在的高层节点
            mark = mark.up;
            // 设置为 新创建的节点的上层节点的 左节点
            // 只有最底层的节点 保存 value ，其他节点只保存 分值即可
            SkipNode up_new = new SkipNode<>(score, null);
            up_new.left = mark;
            up_new.right = mark.right;
            mark.right.left = up_new;
            mark.right = up_new;

            up_new.down = brand_new;
            brand_new.up = up_new;

            // 将当前 全新引用 指向 新创建的 上层的 引用， 如果 while 继续循环，那么 mark 也 已经是 up， 上层的了
            brand_new = up_new;
            ++i;
        }
        ++num;
    }

    public boolean remove(Integer score) {
        SkipNode mark = find(score);
        // 如果 查询到的mark 的 score 与传入的 不同， 表示 根本不存在对应的分值对象， 只是返回了最接近的一个
        if (!mark.score.equals(score)) {
            return true;
        }

        // 查询到的mark 一定是 最底层的链表， 那么就是从最底层开始向上解除关联即 链表删除
        SkipNode del;
        while (mark != null) {
            del = mark.up;
            mark.left.right = mark.right;
            mark.right.left = mark.left;
            // 升一层 如果不为nul 继续处理
            mark = del;
        }
        return true;
    }
}
